package dp

func uniquePaths(m int, n int) int {
	var count int
	dfs(1, 1, m, n, &count)
	return count
}

func dfs(row, col, m, n int, count *int) {
	if row == m && col == n {
		*count++
		return
	}
	if col < n {
		dfs(row, col + 1, m, n, count)
	}
	if row < m {
		dfs(row + 1, col, m, n, count)
	}
}

func uniquePaths2(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		}
	}
	return dp[m - 1][n  -1]
}